package java学习.算法.链表;

import com.sun.source.tree.IfTree;
import org.hamcrest.core.Is;

import java.util.Stack;

/**
 * **************
 * 项目名称: 蓝桥杯 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦 <br/>
 * 创建时间: 2022/3/14 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */
public class Linkedlist {

    class ListNode<V> {
        ListNode next;
        V value;

        public ListNode(V value) {
            this.value = value;
        }
    }

    class DoubleNode<V> {
        DoubleNode next;
        V value;
        DoubleNode prior; // 前一个节点

        public DoubleNode(V value) {
            this.value = value;
        }
    }

    public static ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;    //少于两个节点没有反转的必要。
        }
        ListNode pre = null;
        ListNode cur = head;
        ListNode Next = null;
        while (cur != null) {

            Next = cur.next;
            cur.next = pre;

            pre = cur;
            cur = Next;

        }
        return pre;// 最后cur必然指向NULL，所以返回了pre作为新的头指针
    }

    public static DoubleNode reverseDoubleList(DoubleNode head) {
        if (head == null || head.next == null) {
            return head;    //少于两个节点没有反转的必要。
        }
        DoubleNode pre = null;
        DoubleNode cur = head;
        DoubleNode Next = null;
        while (cur != null) {

            Next = cur.next;
            cur.next = pre;
            cur.prior = Next;

            pre = cur;
            cur = Next;

        }
        return pre;// 最后cur必然指向NULL，所以返回了pre作为新的头指针
    }

    public static ListNode removeNum(ListNode head, int num) {
        /**
         * 1. 先判断 此时的头结点 是否是需要删除的元素
         *   如果是:  head = head.next (向后移)
         *   否则停止。
         * 2，
         **/
        while (head != null) {
            if ((int) head.value != num) {
                break;
            }
            head = head.next;
        }
        ListNode cur = head;
        ListNode pre = head;
        while (cur != null) {

            if ((int) cur.value == num) {
                pre.next = cur.next; // 删除节点
                cur = cur.next;  // cur右移

            } else {
                pre = cur;       // pre移到 cur位置
                cur = cur.next;  // cur右移

            }
        }
        return head; // 返回头结点。删除啊
    }

    public class DoubleList<T> {
        public DoubleNode<T> head;
        public DoubleNode<T> tail;

        // 从头部插入
        public void insertFront(T value) {
            DoubleNode<T> node = new DoubleNode<>(value);
            if (head == null) { // 此时没有节点，添加第一个
                head = node;
                tail = node;

            } else {
                node.next = head;
                head.prior = node;
                head = node;

            }
        }

        // 从头部删除
        public T DeleteFront() {
            if (head == null) { // 此时没有节点
                return null;
            }
            DoubleNode<T> node = head;
            if (head == tail) {
                head = null;
                tail = null;
            } else {                // 头与尾不重合
                head = head.next;
                node.next = null;
                head.prior = null;

            }
            return node.value;
        }


        public void insertTail(T value) {
            DoubleNode<T> node = new DoubleNode<>(value);
            if (tail == null) { // 此时没有节点，添加第一个
                head = node;
                tail = node;

            } else {
                node.prior = tail;
                tail.next = node;
                tail = node;

            }
        }

    }

    //        链表回文判断：
//        仅需中点右侧进栈
    public static boolean linkedHuiwen(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        // 寻找中点：
        ListNode right = head.next;
        ListNode cur = head;
        while (cur.next != null && cur.next.next != null) {
            right = right.next;
            cur = cur.next.next;

        }
        ListNode rightw = right; // 全是下中点
        Stack<ListNode> stack = new Stack<>();
        while (right != null) {
            stack.push(right);
            right = right.next;
        }
        while (!stack.empty()) { // 只要栈不为空
            if (head.value == stack.pop().value) {
                head = head.next;
            }
            return false;
        }
        return true;

    }

    // 不使用栈
    public static boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        // 先找到 中点：
        // 寻找中点：奇：中点；偶：上中点

        ListNode slow = head;
        ListNode fast = head.next;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;

        }
        ListNode slow1 = slow;

        ListNode firstNode = slow.next;  // 第一个需要翻转的节点
        // slow.next = null;
//        翻转
        ListNode pre = null;

        while (firstNode != null) {
            ListNode Next = firstNode.next;
            firstNode.next = pre;
            pre = firstNode;
            firstNode = Next;

        }
        //   firstNode =   reverseListNode(firstNode);
        // 翻转 返回的是 pre；不是 cur
        // firstNode = reverse(firstNode);

        ListNode n3 = pre;
        ListNode cur = head;
        while (cur != null && n3 != null) {
            if (cur.value != n3.value) {
                return false;
            }
            cur = cur.next;
            n3 = n3.next;
        }
        return true;
    }

    /**
     * // 找到链表第一个入环节点，如果无环，返回null
     */
    public static ListNode getLoopNode(ListNode head) {

        if (head == null || head.next == null || head.next.next == null) {
            return null; // 至少三个链表才能产生环
        }
        ListNode slow = head;
        ListNode fast = head.next;

        while (slow != fast) {
            if (fast.next == null || fast.next.next == null) {
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;

        }
        // 跳出： 二者相遇： fast = head; slow 不变
        fast = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        // 跳出： 二者相遇：
//        返回
        return slow;
    }

    /**
     * 如果两个链表都无环，返回第一个相交节点，如果不想交，返回null
     */
    public static ListNode getNoLoopMeetNode(ListNode head1, ListNode head2) {
        if (head1 == null || head2 == null) {
            return null;
        }
        int n = 0;
        ListNode cur1 = head1;
        ListNode cur2 = head2;
        while (cur1.next != null) {
            n++;
            cur1 = cur1.next;
        }
        while (cur2.next != null) {
            n--;
            cur2 = cur2.next;
        }
        if (cur1 != cur2) {
            return null;  // 两个链表结尾不一样 ，则 两链表不相交
        }
        // 谁长，谁的头变成cur1
        cur1 = n > 0 ? head1 : head2;
        // 谁短，谁的头变成cur2
        cur2 = cur1 == head1 ? head2 : head1;
        n = Math.abs(n);
        while (n != 0) {
            n--;
            cur1 = cur1.next; // 使得两链表处于同一起点
        }
        while (cur1 !=cur2){
            cur1 = cur1.next;
            cur2 = cur2.next;

        }
        return  cur1;

    }
    /**
     * 两个有环链表，返回第一个相交节点，如果不想交返回null
     */
    public static ListNode bothLoop(ListNode head1, ListNode loop1,
                                    ListNode head2, ListNode loop2) {

        ListNode cur1 = null;
        ListNode cur2 = null;
        // 类似第一种都无环的情况
        if (loop1 == loop2) {
            cur1 = head1;
            cur2 = head2;
            int n = 0;
            while (cur1 != loop1) {
                n++;
                cur1 = cur1.next;
            }
            while (cur2 != loop2) {
                n--;
                cur2 = cur2.next;
            }
            cur1 = n > 0 ? head1 : head2;
            cur2 = cur1 == head1 ? head2 : head1;
            n = Math.abs(n);
            while (n != 0) {
                n--;
                cur1 = cur1.next;
            }
            while (cur1 != cur2) {
                cur1 = cur1.next;
                cur2 = cur2.next;
            }
            return cur1;

        }else {
            //否则，就是入环节点不一样
            // 找第一个成环节点转回自身的过程中遇到loop2,则相交，否则不相交
            cur1 = loop1.next;
            while (cur1 != loop1) {
                if (cur1 == loop2) {
                    return loop1;
                }
                cur1 = cur1.next;
            }
            return null;
        }
    }


    }
    
